#! /usr/bin/python

import math
import time

t1 = time.time()

def isPrime(n):
    if n==2 or n==3 or n==5 or n==7: return True
    if n==1 or n%2 == 0 or n%3 == 0: return False
    for i in range(5, int(math.sqrt(n))+1, 6):
        if n%i == 0 or n%(i+2) == 0: 
	   return False
    return True

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a%b)

def lastK(n):
    if isPrime(n) or gcd(10, n) != 1: return 0
    x, k = 1, 1
    while x != 0:
          x = (x*10 + 1)%n
	  k += 1
    return k

print lastK(17)
for i in range(10**6+1, 10**7, 2):
    k = lastK(i)
    if k > 10**6:
	print i, k
	break



print time.time() - t1
#print pairs
